
import java.util.ArrayList;
import java.util.Arrays;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Marc Berengueras Campi
 */
public class Algoritmo {
    private int [][]distance; //distancia de levensthein
    private int [][]pasado;
    private Progreso prog;
    public Algoritmo(){
        prog=new Progreso();
    }
    /**
     * Devuelve el porcentage de proceso que llevamos
     * @return prog progreso
     */
    public Progreso getProgreso () {
        return this.prog;
    }



    /**
     * Genera un conjunto de reglas de corrección a partir de un conjunto de pares
     * @param c conjunto de pares
     * @param r reglas
     */
    public void aprendizaje(ConjPares c, Reglas r) throws ExcepcionVacio{
        int n = r.getN();
        int longitud = c.longitud();
        Par p = new Par (null, null);
        for (int i = 0; i < longitud; ++i){
            p = c.getPar(i);
            levenshtein (p.getc1(),p.getc2());
            generarReglas(p.getc1().toCharArray(), p.getc2().toCharArray(), n, r, p.getcontador());
        }
    }

    /**
     * Genera las k palabras candidatas a ser la corrección de la palabra mal escrita
     * @param str1 palabra incorrecta
     * @param d diccionario
     * @param r reglas
     * @param k numero de candidatas a crear
     */
    public ArrayList<StringDouble> cand (char[] str1, Trie d,Reglas r, int k) throws ExcepcionVacio {
  
        int midastr1 = str1.length;
        int alturaDicc = d.GetAltura();
        ArrayList<StringDouble> kcan = new ArrayList<StringDouble>();
        double [][]distancia = new double [midastr1 + 1][alturaDicc + 1];
        boolean existe = r.existeRegla("@".toCharArray());
        distancia[0][0] = 1;
        if (existe){
            /*rellenamos la primera columna de la matriz donde estan las
            probabilidades de @ se convierte en la palabra incorrecta*/
            for (int i = 1; i < midastr1 + 1; ++i){
                char[] beta = null;
                int posini = i -1;
                Trie tbeta = r.getTrieBeta("@");
                double probabilidadMax = buscarBeta (str1, posini, beta, "@".toCharArray(), r, distancia, 0, tbeta);
                distancia[i][0]=probabilidadMax;
            }
        }
        //utilizamos una clase formada por un string y un double donde guardamos las palabras candidatas con sus probabilidades
        StringDouble [] sd = new StringDouble [k];
        for (int l = 0; l < k; ++l) {
            sd[l] = new StringDouble();
            sd[l].d=0.0;
        }
        char [] w = new char [alturaDicc];
       // prog.setFin(false);
        prog.setX(0);
        prog.setN(d.GetPalabras()/3);
        generarProbabilidades (d, distancia, k, str1, 0, r, w, sd);
        prog.setX(prog.getN());
        //prog.setFin(true);
        //funcion para escribir la matriz
       /* for (int i = 0; i < midastr1 +1; ++i){
            for (int j = 0; j < alturaDicc + 1; ++j){
                System.out.print(distancia[i][j] + " ");
            }
            System.out.println();
        }*/
        //funcion para devolver las k candidatas
        for (int cand = 0; cand < k; ++cand){
            if (sd[cand].d != 0.0) {
                kcan.add(sd[cand]);
            }
        }
        return kcan;
    }

    /**
     * Transforma un array de char en otro de la mida midaCadena
     * @param cadena cadena que queremos transformar
     * @param midaCadena mida de la cadena
     * @return la cadena transformada
     */
     private char [] transformarFinal (char [] cadena, int midaCadena){
        char [] aux = new char [midaCadena];
        for (int p = 0; p < midaCadena; ++p) aux[p] = cadena[p];
        return aux;
    }

    /**
     * Para cada beta de la matriz de reglas mira si es igual a una parte de la palabra incorrecta
     * i en caso afirmativo calcula la probabilidad final de transformacion utilizando esta regla;
     * nos quedamos con aquella combinacion que de una probabilidad mayor
     * @param str1 palabra incorrecta
     * @param posini
     * @param reglas conjunto de betas que tienen alpha
     * @param beta beta final que obtenemos
     * @param alpha alpha con la que se han buscado las reglas
     * @param r conjunto completo de reglas
     * @param distancia matriz con las probabilidades
     * @param posicion posicion de la palabra correcta en la que quedamos después de tirar atras mida de alpha veces
     * @return probabilidad maxima con este conjunto de betas
     */
    private double buscarBeta (char[] str1, int posini, char[] beta, char[] alpha, Reglas r,
            double [][] distancia, int posicion, Trie tbeta) throws ExcepcionVacio{
        double probabilidad;
        double probabilidadMax = 0;
        int j = 0;
        int max_beta = r.max_beta;
        beta = new char [str1.length];
        //beta es igual a conjunto vacio
        probabilidad = r.obtenerProb(alpha,"@".toCharArray());
        if (posicion > 0) probabilidad = probabilidad * distancia[posini+1][posicion-1];
        if (probabilidad > probabilidadMax) probabilidadMax = probabilidad;
        boolean exbeta = true;
        for (int posS = posini; posS >= 0 && (posini - posS) < max_beta && exbeta; --posS){
               beta[j]= str1[posS];
               ++j;
               char[] aux2 = transformarFinal (beta, j);
               if (!r.existeReglaBeta2(tbeta, aux2))exbeta=false;
               double probRegla = 0.0;
               if (exbeta) probRegla = r.obtenerProb(alpha,aux2);
               if (probRegla != 0.0) {
                   //posicion 0: columna de la matriz donde estan las probabilidades de conjunto vacio
                   if (posicion == 0){
                       probabilidad = probRegla * distancia[posS][posicion];
                   }
                   //beta es igual a toda la palbra incorrecta
                   else if(posS == -1) {
                       probabilidad = probRegla * distancia[posS][posicion-1];
                   }
                   else {
                       probabilidad = probRegla * distancia[posS][posicion-1];
                   }
                   if (probabilidad > probabilidadMax) probabilidadMax = probabilidad;
              }
        }
        return probabilidadMax;
    }

    /**
     * Inserta de forma ordenada en el array correspondiente una palabra candidata si la probabilidad de esta es
     * mayor de las que ya estan insertadas
     * @param sd array donde guardamos las candidatas
     * @param probw probabilidad de la candidata que queremos añadir
     * @param k numero de candidatas que qeremos
     * @param w palabra candidata que queremos añadir
     */
    private void insertarEnCandidatas (StringDouble[] sd, double probw, int k, char [] w) {
                    int contcand = 1;
                    //miramos si la probabilidad de la palabra es suficientemente grande como para estar
                    //entre las k candidatas y en caso afirmativo la ponemos en el vector de candidatas
                    //ordenada en su posicion corresponidente
                    if (sd[0].d < probw){
                        while (contcand < k && probw > sd[contcand].d) {
                            sd[contcand-1]=sd[contcand];
                            ++contcand;
                        }
                        StringDouble aux = new StringDouble (String.valueOf(w), probw);
                        sd[contcand-1]=aux;
                    }
    }

    /**
     * Genera las alphas a partir de la columna de la matriz que estamos tractando y si
     * existe una regla con esta alpha busca si la correspondiente beta no sirve y, en caso afirmativo,
     * calcula la probabilidad final en la matriz
     * @param posicion posicion dentor de la palabra del diccionario que evaluamos como candidata
     * @param n mida maxima de alpha
     * @param w parte de la palabra del diccionario que evaluamos como candidata que hemos calculado
     * @param str1 palabra incorrecta
     * @param distancia matriz con las probabilidades
     * @param r reglas
     * @throws ExcepcionVacio
     */
    private void buscarAlphas (int posicion, int n, char[] w, char[] str1, double[][] distancia, Reglas r) throws ExcepcionVacio {
        int j = posicion;
        int midastr1 = str1.length;
            char [] alpha;
            char [] aux;
            aux = new char [posicion+1];
            double probabilidadMax = 0;
            //mientras la mida de alpha no sea más grande que n, generamos las alpha y buscamos las reglas
            while (j >= 0 && posicion-j < n){
                alpha = new char [posicion-j+1];
                for (int q = 0; q < posicion-j; ++q){
                    alpha[q]=aux[q];
                }
                alpha[posicion-j] = w[j];
                aux[posicion-j] = w[j];
                boolean existe;
                existe = r.existeRegla(alpha);
                if (existe) {
                    double prob = r.obtenerProb(alpha,"@".toCharArray());
                    if (prob != 0.0){
                        prob *= distancia[0][j];
                        if (distancia[0][posicion+1] < prob) distancia[0][posicion+1] = prob;
                    }
                    Trie tbeta = r.getTrieBeta(String.valueOf(alpha));
                    for (int i = 0; i < midastr1; ++i){
                        if (distancia[i+1][posicion+1] != 1){
                            char[] beta=new char [i];
                            int pos=i;
                            probabilidadMax = buscarBeta (str1, pos, beta, alpha, r, distancia, j+1, tbeta);
                            if (distancia[i+1][posicion+1] < probabilidadMax) distancia[i+1][posicion+1] = probabilidadMax;
                        }
                    }
                   
                }
                --j;
        }
    }

    /**
     *
     * @param diccionario diccionario qe utilizamos
     * @param distancia matriz con las probabilidades
     * @param k numero de candidatas que el usuario quiere
     * @param n mida maxima de alpha
     * @param str1 palabra incorrecta
     * @param posicion posicion de la solucion parcial (palabra del diccionario) en la que nos encontramos
     * @param r conjunto de reglas
     * @param w solucion parcial que tenemos
     * @param sd conjunto donde guardamos las k candidatas y sus probabilidades
     */
    private void generarProbabilidades(Trie diccionario, double[][] distancia, int k, char[] str1, int posicion,
                Reglas r, char [] w, StringDouble[] sd) throws ExcepcionVacio {
        int n = r.getN();
        int midastr1 = str1.length;
        if (diccionario.EsFinPalabra()){
            //si es fin de palabra miramos si hay alguna probabilidad de que sea nuestra candidata
            //en caso afirmativo miramos si esta entre las k con mas probabilidades
            //if (distancia[midastr1][posicion] != 0) System.out.println(String.valueOf(w));
             double probw = distancia[midastr1][posicion];
             if (probw > 0){
                insertarEnCandidatas (sd, probw, k, w);
             }
             double X = prog.getX();
             ++X;
             prog.setX(X);
        }
        else {
            char letra = diccionario.GetChar();
            w[posicion]=letra;
            for (int i = 0; i < midastr1; ++i){
                if (str1[i] == letra) {
                    distancia [i+1][posicion+1] = distancia[i][posicion];
                }
            }
            buscarAlphas (posicion, n, w, str1, distancia, r);
            Trie hijo = diccionario.GetSiguienteHijo();
            generarProbabilidades(hijo, distancia, k, str1, posicion + 1, r, w, sd);
            w[posicion] = ' ';
            Trie hermano = diccionario.GetSiguienteHermano();
            for (int i = -1; i < midastr1; ++i) distancia[i+1][posicion+1] = 0;
            if (hermano != null) {
                generarProbabilidades(hermano, distancia, k, str1, posicion, r, w, sd);
            }
        }
    }

/*
 * busca todas las reglas que puede encontrar dentro la matriz que nos muestra el camino de levenshtein 
 * entre dos palabras
 * @param str1 palabra incorrecta
 * @param str2 palabra correcta
 * @param n mida de alpha
 */
private void buscaReglas(char[] str1, char[] str2, int n, Reglas r, int cont) throws ExcepcionVacio{
    //recorremos la matriz que nos muestra el camino de levensthein
    String salpha;
    String sbeta;
    int jant = 0;
    for(int i = 0; i < str1.length+1; ++i) {
        boolean encontrado = false;
        char alpha[];
        char beta [];
        alpha = new char[n+20];
        beta= new char [n+20]; 
        int midaalpha = 0;
        int midabeta = 0;
        for (int j = 0; j <str2.length+1 && !encontrado; ++j){
            //si encontramos un uno quiere decir que hemos encontrado el camino
            if (pasado[i][j] == 1 && (i != 0 || j != 0)) {
                int k = i;
                boolean finish = false;
                //caso de elimiación de un caracter
                if (k > 0 && pasado[k-1][j] == 1){
                    char[] aux = new char[1];
                    aux[0]= str1[i-1];
                    r.anadirRegla(String.valueOf(aux), "@", cont);
                    //printRegla(aux,"@".toCharArray(),1,1);
                }
                /*if (j+1 < str2.length+1 && pasado[k][j+1] == 1){
                        char[] aux = new char[1];
                        aux[0]= str2[j-1];
                        r.anadirRegla("@", String.valueOf(aux), cont);
                        //printRegla("@".toCharArray(), aux,1,1);
                }*/
                //desde el punto del camino encontrado miramos la submatriz de mida [str1.length][n]
                // i buscamos todas las posibles alphas y correspondientes betas
                boolean jmodif = true;
                while (midaalpha <= n && !finish && i+midaalpha-1 <= str1.length){
                    //caso de añadir un caracter
                    if (j > 0 && pasado[k][j-1] == 1 && jant < j){
                        jant = j;
                        char[] aux = new char[1];
                        aux[0]= str2[j-1];
                        r.anadirRegla("@", String.valueOf(aux), cont);
                        //printRegla("@".toCharArray(), aux,1,1);
                    }
                    // caso de principio de camino en el que no se produce una eliminacion
                    if ((k >= 1 && pasado[k-1][j] == 0 && !encontrado)) {
                        alpha[midaalpha] = str1[k-1];
                        beta[midabeta] = str2[j-1];
                        encontrado = true;
                        ++midaalpha;
                        ++midabeta;
                        salpha = transformarString (alpha, midaalpha);
                        sbeta = transformarString (beta, midabeta);
                        jmodif = false;
                        if (!salpha.equals(sbeta))r.anadirRegla(salpha,sbeta, cont);
                    }
                    else {
                        encontrado = true;
                        //caso en el que se incrementan alpha y beta
                        if (k+1 <= str1.length && j+1 <= str2.length && pasado[k+1][j+1] == 1 && midaalpha<n) {
                             ++k;
                             ++j;
                             alpha[midaalpha] = str1[k-1];
                             beta[midabeta] = str2[j-1];
                             ++midaalpha;
                             ++midabeta;
                             jmodif = true;
                        }
                        //caso en el que solo se incrementa alpha
                        else if(k + 1 <= str1.length && pasado[k + 1][j] == 1 && midaalpha < n) {
                            ++k;
                            alpha[midaalpha] = str1[k-1];
                            ++midaalpha;
                            jmodif = false;
                        }
                        //caso en el que solo se incrementa beta
                        else if(j + 1 <= str2.length && pasado[k][j + 1] == 1) {
                            ++j;
                            beta[midabeta] = str2[j-1];
                            ++midabeta;
                            jmodif = true;
                        }
                        //caso en el que no se produce ningun cambio ni en alpha ni en beta
                        else {
                            jmodif = false;
                            finish = true;
                        }
                        if (!finish) {
                            salpha = transformarString (alpha, midaalpha);
                            sbeta = transformarString (beta, midabeta);
                            if (!salpha.equals(sbeta) && midabeta > 0 && midaalpha > 0) {
                                r.anadirRegla(salpha, sbeta, cont);
                            }
                        }
                    }
                }
            }
        }
    }
}

    private String transformarString (char [] cadena, int midaCadena){
        char [] aux = new char [midaCadena];
        for (int p = 0; p < midaCadena; ++p) aux[p] = cadena[p];
        String resultado = String.valueOf(aux);
        return resultado;
    }

    private boolean check(char[] str1, char[] str2,pair sig, pair act, ArrayList<pair> pos,int n, int m){
        if (!(sig.first>=0 && sig.first<n)) return false;
        if (!(sig.second>=0 && sig.second<m)) return false;
        if (pasado[sig.first][sig.second]==1) return false;
        if (act.first==sig.first && act.second>sig.second)
            if (!(distance[sig.first][sig.second]<distance[act.first][act.second])) return false;
        if (act.first>sig.first && act.second==sig.second)
            if (!(distance[sig.first][sig.second]<distance[act.first][act.second])) return false;
        if (act.first>sig.first && act.second>sig.second){
            if (str2[act.second-1]==str1[act.first-1])
                 if (!(distance[sig.first][sig.second]==distance[act.first][act.second])) return false;
            if (str2[act.second-1]!=str1[act.first-1])
                 if (!(distance[sig.first][sig.second]<distance[act.first][act.second])) return false;
        }
        pos.add(sig);
        pasado[sig.first][sig.second]=1;
        return true;
    }
    private void generarReglas (char [] str1, char [] str2, int nn, Reglas r, int cont) throws ExcepcionVacio {
        int n=str1.length+1;
        int m=str2.length+1;
        pasado = new int[n][m];
        for (int i=0; i< n; i++)
               for (int j=0; j<m; j++)
                    pasado[i][j]=0;
        ArrayList<pair> pos;
        pos = new ArrayList<pair>();
        pos.add(new pair(n-1,m-1));
        pasado[n-1][m-1]=1;
        boolean encontrado=false;
        while (!pos.isEmpty() && !encontrado){
            pair act = pos.get(pos.size()-1);
            pos.remove(pos.size()-1);
            if (check(str1,str2,new pair(act.first,act.second-1),act,pos,n,m)){
                } else if (check(str1, str2, new pair(act.first - 1, act.second), act, pos, n, m)){
                } else { check(str1, str2, new pair(act.first - 1, act.second - 1), act, pos, n, m);
                }
        }
       /* for(int i = 0; i < pasado.length; ++i){
            for (int j = 0; j < pasado[i].length; ++j){
                System.out.print(pasado[i][j]+ " ");
            }
            System.out.println();
        }
        System.out.println();*/
        buscaReglas(str1, str2, nn, r, cont);

    }

    private int minimum(int a, int b, int c) {
        if(a<=b && a<=c)
        {
            return a;
        }
        if(b<=a && b<=c)
        {
            return b;
        }
        return c;
    }

    private void levenshtein(String str1, String str2) {
        levenshtein(str1.toCharArray(),
                                          str2.toCharArray());
    }

    private void levenshtein(char [] str1, char [] str2) {
        distance = new int[str1.length+1][str2.length+1];

        for(int i=0;i<=str1.length;i++)
        {
                distance[i][0]=i;
        }
        for(int j=0;j<=str2.length;j++)
        {
                distance[0][j]=j;
        }
        for(int i=1;i<=str1.length;i++)
        {
            for(int j=1;j<=str2.length;j++)
            {
                  distance[i][j]= minimum(distance[i-1][j]+1,
                                        distance[i][j-1]+1,
                                        distance[i-1][j-1]+
                                        ((str1[i-1]==str2[j-1])?0:1));
            }
            
        }

    }
    
}
